{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #追逐游戏"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph #topological-sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图 #拓扑排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: chaseGame"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #追逐游戏"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "秋游中的小力和小扣设计了一个追逐游戏。他们选了秋日市集景区中的 N 个景点，景点编号为 1~N。此外，他们还选择了 N 条小路，满足任意两个景点之间都可以通过小路互相到达，且不存在两条连接景点相同的小路。整个游戏场景可视作一个无向连通图，记作二维数组 `edges`，数组中以 `[a,b]` 形式表示景点 a 与景点 b 之间有一条小路连通。\r\n",
    "\r\n",
    "小力和小扣只能沿景点间的小路移动。小力的目标是在最快时间内追到小扣，小扣的目标是尽可能延后被小力追到的时间。游戏开始前，两人分别站在两个不同的景点 `startA` 和 `startB`。每一回合，小力先行动，小扣观察到小力的行动后再行动。小力和小扣在每回合可选择以下行动之一：\r\n",
    "- 移动至相邻景点\r\n",
    "- 留在原地\r\n",
    "\r\n",
    "如果小力追到小扣（即两人于某一时刻出现在同一位置），则游戏结束。若小力可以追到小扣，请返回最少需要多少回合；若小力无法追到小扣，请返回 -1。\r\n",
    "\r\n",
    "注意：小力和小扣一定会采取最优移动策略。\r\n",
    "\r\n",
    "**示例 1：**\r\n",
    ">输入：`edges = [[1,2],[2,3],[3,4],[4,1],[2,5],[5,6]], startA = 3, startB = 5`\r\n",
    ">\r\n",
    ">输出：`3`\r\n",
    ">\r\n",
    ">解释：\r\n",
    ">![image.png](https://pic.leetcode-cn.com/1597991318-goeHHr-image.png){:height=\"250px\"}\r\n",
    ">\r\n",
    ">第一回合，小力移动至 2 号点，小扣观察到小力的行动后移动至 6 号点；\r\n",
    ">第二回合，小力移动至 5 号点，小扣无法移动，留在原地；\r\n",
    ">第三回合，小力移动至 6 号点，小力追到小扣。返回 3。\r\n",
    "\r\n",
    "\r\n",
    "**示例 2：**\r\n",
    ">输入：`edges = [[1,2],[2,3],[3,4],[4,1]], startA = 1, startB = 3`\r\n",
    ">\r\n",
    ">输出：`-1`\r\n",
    ">\r\n",
    ">解释：\r\n",
    ">![image.png](https://pic.leetcode-cn.com/1597991157-QfeakF-image.png){:height=\"250px\"}\r\n",
    ">\r\n",
    ">小力如果不动，则小扣也不动；否则小扣移动到小力的对角线位置。这样小力无法追到小扣。\r\n",
    "\r\n",
    "**提示：**\r\n",
    "- `edges` 的长度等于图中节点个数\r\n",
    "- `3 <= edges.length <= 10^5`\r\n",
    "- `1 <= edges[i][0], edges[i][1] <= edges.length 且 edges[i][0] != edges[i][1]`\r\n",
    "- `1 <= startA, startB <= edges.length 且 startA != startB`\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [Za25hA](https://leetcode.cn/problems/Za25hA/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [Za25hA](https://leetcode.cn/problems/Za25hA/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2],[2,3],[3,4],[4,1],[2,5],[5,6]]\\n3\\n5', '[[1,2],[2,3],[3,4],[4,1]]\\n1\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chaseGame(self, edges: List[List[int]], startA: int, startB: int) -> int:\n",
    "        n = max(max(i) for i in edges)\n",
    "        grid = [set() for i in range(n + 1)]\n",
    "        for i, j in edges:\n",
    "            grid[i].add(j)\n",
    "            grid[j].add(i)\n",
    "        \n",
    "        def bfs(start):\n",
    "            res = [-1] * (n + 1)\n",
    "            que = collections.deque([start])\n",
    "            res[start] = 0\n",
    "            while que:\n",
    "                p = que.popleft()\n",
    "                for i in grid[p]:\n",
    "                    if res[i] == -1:\n",
    "                        res[i] = res[p] + 1\n",
    "                        que.append(i)\n",
    "            return res\n",
    "        la, lb = bfs(startA), bfs(startB)\n",
    "        if la[startB] == 1: return 1\n",
    "        res = 1\n",
    "        for i, j in zip(la, lb):\n",
    "            if i - j > 1:\n",
    "                res = max(res, i)\n",
    "        que = []\n",
    "        for i in range(1, n + 1):\n",
    "            if len(grid[i]) == 1:\n",
    "                que.append(i)\n",
    "        while que:\n",
    "            x = que.pop()\n",
    "            for i in grid[x]:\n",
    "                grid[i].remove(x)\n",
    "                if len(grid[i]) == 1:\n",
    "                    que.append(i)\n",
    "            grid[x].pop()\n",
    "        que = []\n",
    "        for i in range(1, n + 1):\n",
    "            if len(grid[i]) > 1:\n",
    "                que.append(i)\n",
    "        def dfs(start, leave, pre, target):\n",
    "            if leave == 0: return True\n",
    "            for i in grid[start]:\n",
    "                if i == pre: continue\n",
    "                if i == target: return False\n",
    "                if not dfs(i, leave-1, start, target):\n",
    "                    return False\n",
    "            return True\n",
    "        for i in que:\n",
    "            if la[i] - lb[i] < 2: continue\n",
    "            if dfs(i, 3, -1, i):\n",
    "                return -1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chaseGame(self, edges: List[List[int]], startA: int, startB: int) -> int:\n",
    "        n = max(max(i) for i in edges)\n",
    "        grid = [set() for i in range(n + 1)]\n",
    "        for i, j in edges:\n",
    "            grid[i].add(j)\n",
    "            grid[j].add(i)\n",
    "        \n",
    "        def bfs(start):\n",
    "            res = [-1] * (n + 1)\n",
    "            que = collections.deque([start])\n",
    "            res[start] = 0\n",
    "            while que:\n",
    "                p = que.popleft()\n",
    "                for i in grid[p]:\n",
    "                    if res[i] == -1:\n",
    "                        res[i] = res[p] + 1\n",
    "                        que.append(i)\n",
    "            return res\n",
    "        la, lb = bfs(startA), bfs(startB)\n",
    "        if la[startB] == 1: return 1\n",
    "        res = 1\n",
    "        for i, j in zip(la, lb):\n",
    "            if i - j > 1:\n",
    "                res = max(res, i)\n",
    "        que = []\n",
    "        for i in range(1, n + 1):\n",
    "            if len(grid[i]) == 1:\n",
    "                que.append(i)\n",
    "        while que:\n",
    "            x = que.pop()\n",
    "            for i in grid[x]:\n",
    "                grid[i].remove(x)\n",
    "                if len(grid[i]) == 1:\n",
    "                    que.append(i)\n",
    "            grid[x].pop()\n",
    "        que = []\n",
    "        for i in range(1, n + 1):\n",
    "            if len(grid[i]) > 1:\n",
    "                que.append(i)\n",
    "        def dfs(start, leave, pre, target):\n",
    "            if leave == 0: return True\n",
    "            for i in grid[start]:\n",
    "                if i == pre: continue\n",
    "                if i == target: return False\n",
    "                if not dfs(i, leave-1, start, target):\n",
    "                    return False\n",
    "            return True\n",
    "        for i in que:\n",
    "            if la[i] - lb[i] < 2: continue\n",
    "            if dfs(i, 3, -1, i):\n",
    "                return -1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def chaseGame(self, edges: List[List[int]], startA: int, startB: int) -> int:\r\n",
    "        n = max(max(i) for i in edges)\r\n",
    "        grid = [set() for i in range(n + 1)]\r\n",
    "        for i, j in edges:\r\n",
    "            grid[i].add(j)\r\n",
    "            grid[j].add(i)\r\n",
    "        \r\n",
    "        def bfs(start):\r\n",
    "            res = [-1] * (n + 1)\r\n",
    "            que = collections.deque([start])\r\n",
    "            res[start] = 0\r\n",
    "            while que:\r\n",
    "                p = que.popleft()\r\n",
    "                for i in grid[p]:\r\n",
    "                    if res[i] == -1:\r\n",
    "                        res[i] = res[p] + 1\r\n",
    "                        que.append(i)\r\n",
    "            return res\r\n",
    "        la, lb = bfs(startA), bfs(startB)\r\n",
    "        if la[startB] == 1: return 1\r\n",
    "        res = 1\r\n",
    "        for i, j in zip(la, lb):\r\n",
    "            if i - j > 1:\r\n",
    "                res = max(res, i)\r\n",
    "        que = []\r\n",
    "        for i in range(1, n + 1):\r\n",
    "            if len(grid[i]) == 1:\r\n",
    "                que.append(i)\r\n",
    "        while que:\r\n",
    "            x = que.pop()\r\n",
    "            for i in grid[x]:\r\n",
    "                grid[i].remove(x)\r\n",
    "                if len(grid[i]) == 1:\r\n",
    "                    que.append(i)\r\n",
    "            grid[x].pop()\r\n",
    "        que = []\r\n",
    "        for i in range(1, n + 1):\r\n",
    "            if len(grid[i]) > 1:\r\n",
    "                que.append(i)\r\n",
    "        def dfs(start, leave, pre, target):\r\n",
    "            if leave == 0: return True\r\n",
    "            for i in grid[start]:\r\n",
    "                if i == pre: continue\r\n",
    "                if i == target: return False\r\n",
    "                if not dfs(i, leave-1, start, target):\r\n",
    "                    return False\r\n",
    "            return True\r\n",
    "        for i in que:\r\n",
    "            if la[i] - lb[i] < 2: continue\r\n",
    "            if dfs(i, 3, -1, i):\r\n",
    "                return -1\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chaseGame(self, edges: List[List[int]], startA: int, startB: int) -> int:\n",
    "        n = len(edges)\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "            if x == startA and y == startB:\n",
    "                return 1\n",
    "            if x == startB and y == startA:\n",
    "                return 1\n",
    "\n",
    "\n",
    "        fa = [-1] * (n + 1)\n",
    "        h = [0] * (n + 1)\n",
    "        in_loop = [False] * (n + 1)\n",
    "        loop = 0\n",
    "        def dfs(x, p):\n",
    "            nonlocal loop\n",
    "\n",
    "            if p != -1:\n",
    "                fa[x] = p\n",
    "                h[x] = h[p] + 1\n",
    "            for y in g[x]:\n",
    "                if y == p:\n",
    "                    continue\n",
    "                if h[y] == 0:\n",
    "                    dfs(y, x)\n",
    "                elif h[y] < h[x]:\n",
    "                    while x != y:\n",
    "                        in_loop[x] = True\n",
    "                        x = fa[x]\n",
    "                        loop += 1\n",
    "                    in_loop[y] = True\n",
    "                    loop += 1\n",
    "        h[1] = 1\n",
    "        dfs(1, -1)\n",
    "\n",
    "        def bfs(u, loop_st):\n",
    "            dist = [inf] * (n + 1)\n",
    "            dist[u] = 0\n",
    "            q = []\n",
    "            q.append(u)\n",
    "            while q:\n",
    "                x = q.pop(0)\n",
    "                if loop_st and in_loop[x]:\n",
    "                    return [x, dist[x]]\n",
    "                for y in g[x]:\n",
    "                    if dist[y] <= dist[x] + 1:\n",
    "                        continue\n",
    "                    dist[y] = dist[x] + 1\n",
    "                    q.append(y)\n",
    "            return dist\n",
    "        \n",
    "        da = bfs(startA, False)\n",
    "        db = bfs(startB, False)\n",
    "        stB, dist_stB = bfs(startB, True)\n",
    " \n",
    "\n",
    "        if loop >= 4 and da[stB] >= dist_stB + 1:\n",
    "            return -1\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(1, n + 1):\n",
    "            if da[i] > db[i] + 1:\n",
    "                res = max(res, da[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "INF = float('inf')\n",
    "\n",
    "class Solution:\n",
    "    def chaseGame(self, edges: List[List[int]], startA: int, startB: int) -> int:\n",
    "        n = len(edges)\n",
    "        adj = [[] for _ in range(n+1)]\n",
    "        for v in edges:\n",
    "            adj[v[0]].append(v[1])\n",
    "            adj[v[1]].append(v[0])\n",
    "            if (v[0] == startA and v[1] == startB) or (v[0] == startB and v[1] == startA):\n",
    "                return 1\n",
    "\n",
    "        depth = [0] * (n + 1)\n",
    "        parent = [0] * (n + 1)\n",
    "        in_loop = [False] * (n + 1)\n",
    "        loop = 0\n",
    "\n",
    "        def dfs(u, p):\n",
    "            nonlocal loop\n",
    "            parent[u] = p\n",
    "            depth[u] = depth[p] + 1\n",
    "            for v in adj[u]:\n",
    "                if v == p:\n",
    "                    continue\n",
    "                if not depth[v]:\n",
    "                    dfs(v, u)\n",
    "                elif depth[v] < depth[u]:\n",
    "                    cu = u\n",
    "                    while cu != v:\n",
    "                        in_loop[cu] = True\n",
    "                        loop += 1\n",
    "                        cu = parent[cu]\n",
    "                    in_loop[v] = True\n",
    "                    loop += 1\n",
    "\n",
    "        def bfs(u, detect_loop):\n",
    "            dist = [INF] * (n + 1)\n",
    "            q = deque([u])\n",
    "            dist[u] = 0\n",
    "            while q:\n",
    "                x = q.popleft()\n",
    "                if detect_loop and in_loop[x]:\n",
    "                    return x, dist[x]\n",
    "                for y in adj[x]:\n",
    "                    if dist[y] <= dist[x] + 1:\n",
    "                        continue\n",
    "                    dist[y] = dist[x] + 1\n",
    "                    q.append(y)\n",
    "            return dist\n",
    "\n",
    "        dfs(1, 0)\n",
    "        da = bfs(startA, False)\n",
    "        db = bfs(startB, False)\n",
    "        if loop >= 4:\n",
    "            qb = bfs(startB, True)\n",
    "            if qb[1] + 1 < da[qb[0]]:\n",
    "                return -1\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            if da[i] > db[i] + 1:\n",
    "                ans = max(ans, da[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chaseGame(self, edges: List[List[int]], startA: int, startB: int) -> int:\n",
    "        n = len(edges)\n",
    "        neighbors = [[] for _ in range(n)]\n",
    "        for i, j in edges:\n",
    "            neighbors[i - 1].append(j - 1)\n",
    "            neighbors[j - 1].append(i - 1)\n",
    "        startA -= 1\n",
    "        startB -= 1\n",
    "        if startA == startB: return 0\n",
    "        if startA in neighbors[startB]: return 1\n",
    "        def bfs(s):\n",
    "            dist = [-1] * n\n",
    "            dist[s] = 0\n",
    "            q = deque([s])\n",
    "            while len(q) > 0:\n",
    "                i = q.popleft()\n",
    "                for j in neighbors[i]:\n",
    "                    if dist[j] > -1: continue\n",
    "                    dist[j] = dist[i] + 1\n",
    "                    q.append(j)\n",
    "            return dist\n",
    "        distA, distB = bfs(startA), bfs(startB)\n",
    "        circle = set()\n",
    "        visit = [False] * n\n",
    "        def dfs(i, pa):\n",
    "            if visit[i]:\n",
    "                circle.add(i)\n",
    "                return True\n",
    "            visit[i] = True\n",
    "            for j in neighbors[i]:\n",
    "                if pa == j: continue\n",
    "                if dfs(j, i):\n",
    "                    if i in circle:\n",
    "                        return False\n",
    "                    else:\n",
    "                        circle.add(i)\n",
    "                        return True\n",
    "            return False\n",
    "        dfs(0, -1)\n",
    "        nearest = -1\n",
    "        nl = n\n",
    "        for i in circle:\n",
    "            if distB[i] < nl:\n",
    "                nl = distB[i]\n",
    "                nearest = i\n",
    "        if len(circle) > 3 and (distB[nearest] < distA[nearest] - 1): \n",
    "            return -1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if distA[i] - 1 > distB[i]:\n",
    "                ans = max(ans, distA[i])\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
